#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=50010,MAXM=200010,MAXNUM=1000010;
int n,m,maxnum,a[MAXN],sum[MAXN],nxt[MAXN],fst[MAXNUM];
struct queryy
{
    int num,l,r,ans;
}quer[MAXM];
bool cmp1(queryy a,queryy b)
{
    return a.l<b.l;
}
bool cmp2(queryy a,queryy b)
{
    return a.num<b.num;
}
int lowbit(int x)
{
    return x&-x;
}
void change(int o,int x)
{
    while(o<=n)
    {
        sum[o]+=x;
        o+=lowbit(o);
    }
    return;
}
int query(int o)
{
    int ans=0;
    while(o>0)
    {
        ans+=sum[o];
        o-=lowbit(o);
    }
    return ans; 
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;++i)
    {
        scanf("%d",&a[i]);
        maxnum=max(maxnum,a[i]);
    }
    for(int i=n;i>=1;--i)
    {
        nxt[i]=fst[a[i]];
        fst[a[i]]=i;
    }
    for(int i=1;i<=maxnum;++i)
        if(fst[i])change(fst[i],1);
    scanf("%d",&m);
    for(int i=1;i<=m;++i)
    {
        scanf("%d%d",&quer[i].l,&quer[i].r);
        quer[i].num=i;
    }
    sort(quer+1,quer+1+m,cmp1);
    for(int i=1;i<=m;++i)
    {
        for(int j=quer[i-1].l;j<quer[i].l;++j)
            if(nxt[j])change(nxt[j],1);
        quer[i].ans=query(quer[i].r)-query(quer[i].l-1);
    }
    sort(quer+1,quer+1+m,cmp2);
    for(int i=1;i<=m;++i)
        printf("%d\n",quer[i].ans);
    return 0;
}
